翻訳と辞書 Words near each other ・ Defecation (band) ・ Defecation postures ・ Defecography ・ Defect ・ Defect concentration diagram ・ Defect criticality ・ Defect Designer ・ Defect detector ・ Defect of Birth ・ Defect tracking ・ Defected Records ・ Defection ・ Defection (song) ・ Defective ・ Defective by Design ・ Defective coloring ・ Defective democracy ・ Defective Epitaph ・ Defective interfering particle ・ Defective matrix ・ Defective on arrival ・ Defective pixel ・ Defective Premises Act 1972 ・ Defective script ・ Defective verb ・ Defector (album) ・ Defector (disambiguation) ・ Defector (song) ・ Defectors (game show) ・ Defectors from the French army to the ALN Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Defective coloring ： ウィキペディア英語版 Defective coloring In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent. (See here for Glossary of graph theory) ==History== Defective coloring was introduced nearly simultaneously by Burr and Jacobson, Harary and Jones and Cowen, Cowen and Woodall.〔 Surveys of this and related colorings are given by Marietjie Frick. Cowen, Cowen and Woodall 〔 focused on graphs embedded on surfaces and gave a complete characterization of all ''k'' and ''d'' such that every planar is (''k'', ''d'')-colorable. Namely, there does not exist a ''d'' such that every planar graph is (1, ''d'')- or (2, ''d'')-colorable; there exist planar graphs which are not (3, 1)-colorable, but every planar graph is (3, 2)-colorable. Together with the (4, 0)-coloring implied by the Four color theorem, this solves defective chromatic number for the plane. Poh and Goddard showed that any planar graph has a special (3,2)-coloring in ehich each color class is a linear forest, and this can be obtained from a more general result of Woodall. For general surfaces, it was shown that for each genus $g\; \backslash geq\; 0$, there exists a $k=k(g)$ such that every graph on the surface of genus $g$ is (4, ''k'')-colorable.〔 This was improved to (3, ''k'')-colorable by Archdeacon. For general graphs, a result of László Lovász from the 1960s, which has been rediscovered many times provides a ''O(∆E)''-time algorithm for defective coloring graphs of maximum degree ∆. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Defective coloring」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.